package org.hot100_0.leetcode46;

import javax.sound.midi.Soundbank;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

    public static void main(String[] args) {
        Solution test = new Solution();
        int [] nums={1,2,1};
        List<List<Integer>> lists = test.permute(nums);

        for (List<Integer> list: lists){
            for (int num:list) {
                System.out.println(num);
            }

            System.out.println("-------------");
        }
    }

    /**
     * 全排列 有重复数字 、 没有重复数字
     */
    public List<List<Integer>> permute(int[] nums) {

        int n = nums.length;

        boolean[] used = new boolean[n];

        Arrays.fill(used,false);

        Arrays.sort(nums);

        backtracking(nums,used);

        return res;
    }

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> item = new ArrayList<>();

    private void backtracking(int[] nums, boolean[] used) {

        if (item.size() == nums.length) {
            res.add(new ArrayList<>(item));
            return;
        }

        for (int i = 0; i < nums.length; i++) {

            if ( i!=0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }

            if (used[i]==false){
                item.add(nums[i]);
                used[i]=true;
                backtracking(nums, used);
                used[i] = false;
                item.remove(item.size()-1);
            }
        }

    }
}
